// 冒泡排序
let arr = [9,8,7,6,5]
function swap(arr, j, k) {
  let temp = arr[j]
  arr[j] = arr[k]
  arr[k] = temp
}
function Bubble(arr) {
  for(let i=0; i<arr.length; i++){
    for(let j=0; j<arr.length-i-1; j++) {
      if(arr[j]>arr[j+1]) {
        swap(arr, j, j+1)
      }
    }
  }
  console.log(arr)
}
// Bubble(arr)

// 选择排序 
// 第一个是最小值  然后向后面查找 找到最小的值 交换位置
function choice(arr) {
  for(let i = 0; i<arr.length - 1; i++) {
    let min = i
    let k = i+1
    while(k < arr.length) {
      if(arr[k]<arr[min]) {
        min = k
      }
      swap(arr, i, min)
      k++
    }
  }
  console.log(arr)
}
// choice(arr)

// 插入排序
// 假设前面是排序好的 后面的数往前面比较  直到遇见没比这个大的 就插入到这个位置
function insertion(arr) {
  for(let i = 0; i<arr.length-1; i++) {
    // let num = arr [i]
    let k = i+1
    let num = arr[k]
    while(k>0 && arr[k-1] > num) {
      arr[k] = arr[k-1]
      k--
    }
    arr[k] = num
  }
  console.log(arr)
}
// insertion(arr)


function myMerge(A, l, r, m) {
  let A1 = A.slice(l, m)
  let A2 = A.slice(m, r)
  A1.push(Number.POSITIVE_INFINITY)
  A2.push(Number.POSITIVE_INFINITY)
  let k=0,j = 0;
  while(l<r){
    A[l] = A1[k]>A2[j] ? A2[j++] : A1[k++]
    l++
  }
}

function merge_rec(A, left, right) {
  if(right-left < 2) return A
  let mid = Math.floor((left+right)/2)
  merge_rec(A, left, mid)
  merge_rec(A, mid, right)
  myMerge(A, left, right, mid)
}

// merge_rec(arr, 0, arr.length)
// console.log(arr)

// 快速排序
function quick(A, l, r) {
  let pri = l
  let j = l+1
  let k = r-1
  while(j<=k) {
    if(A[j]>A[pri]){
      swap(A, j, k--)
    }else{
      j++
    } 
  }
  swap(A, k, pri)
  return k
}

function quick_rc(A, l, r) {
  if(r-l < 2) return A
  let index = quick(A, l, r)
  // console.log(index)
  quick_rc(A, l, index)
  quick_rc(A, index+1, r)

}
quick_rc(arr, 0, arr.length)
console.log(arr)





// 合并排序
function merge(A, l, mid, r) {
  let B = A.slice(l, mid)
  let C = A.slice(mid, r)
  B.push(Number.POSITIVE_INFINITY)
  C.push(Number.POSITIVE_INFINITY)
  let k = 0
  let j = 0
  for (let i = l; i < r; i++) {
    // 相当于A是一个空数组 往里面塞数据
    A[i] = B[k] > C[j] ? C[j++] : B[k++]
  }
}

function merge_sort(A, l, r) {
  if (r - l < 2) return
  let mid = ~~((l + r) / 2)
  merge_sort(A, l, mid)
  merge_sort(A, mid, r)
  merge(A, l, mid, r)
}


function xx(A, l, r) {
  let prov = A[r - 1]
  let j = l;
  let k = r - 1;
  while (j < k) {
    if (A[j] > prov) {
      swap(A, j, --k)
    } else {
      j++
    }
  }
  swap(A, k, r - 1)
  return k
}
// 
function q_sort(A, l, r) {
  if (r - l < 2) return
  let index = xx(A, l, r)
  q_sort(A, l, index)
  q_sort(A, index + 1, r)
}